package com.zzz.offer.recover;

public class Cover {
    public static void main(String[] args) {
        System.out.println(new Cover().rectCover(3));
    }

    public int rectCover(int target) {
        // 将问题转化成子问题
        // 比如题目要求
        //我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，从同一个方向看总共有多少种不同的方法？
        //
        //比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：

        // 所以可得出结论，矩形的必须是2 * n 这个2很关键
        // 这个2 可以有两种方式
        // 第一种 小矩形竖着放  那么剩下的 n-1 的小矩形也是必须 2*n 的形式摆放
        // 第二种 两个小矩形横着放，然后后面跟着 剩余的 (n -2) 个摆放，也必须是2*n 的方式
        // 当n=0   0
        // 当n=1   1  只能竖着放
        // 当n=2   [1 + f(1) ] 和 [ 2 ]  这两种
        // 当n=3   [1 + f(2)] 和 [2 + f(1)]
        // ...
        // 当n=n   [1 + f(n-1)]  和 [2 + f(n-2)]


        if (target <= 2) {
            return target;
        }

        int first = 1;
        int second = 2;
        int way = 0;

        while (target > 2) {
            way = first + second;
            first = second;
            second = first;
            target--;
        }

        return way;
    }
}
